In industrial production, data processing and communication, most processes encountered involve carrying out multiple tasks with limited resources. It is therefore necessary to assign the limited resources to the tasks in a manner that assures implementation of the process in the most efficient manner. In processes involving only a few tasks, decisions as to resource assignment and task sequencing are made through manual analysis. As is well known, such manual analysis is not sufficient to optimize processes where the number of tasks and interrelationships among the tasks are relatively complex. For example, it is a simple matter to arrange an examination schedule for a small group of students at an educational institution. Optimizing the scheduling of examinations for thousands of students at a large university, however, presents a difficult problem.
U.S. Pat. No. 4,744,028, issued to N. K. Kamarkar May 10, 1988, describes several linear programming methods adapted to scheduling problems and discloses a method and apparatus for optimizing resource allocation which extends the use of linear programming to the interior of a solution space polytope and iteratively determines an optimum solution by steepest descent analysis. The allocation method is particularly useful in allocation systems too large for practical implementation by linear programming methods.
Another technique known as "graph coloring" has been applied to resource allocation problems. Graph coloring is generally described in the article "An upper bound for the chromatic number of a graph and its application to timetabling problems" by D. J. A. Welsh and M. B. Powell appearing in the Computer Journal, Volume No. 10, 1967 at pages 85-86. It involves the formation of a graph having nodes representing objects joined by lines representing constraints describing the pairwise compatibility of each object with every other object.
U.S. Pat. No. 4,571,678, issued to G. J. Chaitin Feb. 18, 1986, discloses a register allocation and spilling scheme via graph coloring for an optimizing compiler that receives a high level source language and produces machine interpretable instruction. Computational data is assigned to a limited number of high speed computer registers where not enough such registers are available to store all the required data at a point in time. Register assignments are made building a register interference graph, coalescing nodes of the graph and coloring the graph using graph reduction techniques. If the number of registers is insufficient, the costs of using memory for each register is estimated and the graph is reconstructed until an acceptable allocation is made. U.S. Pat. No. 4,782,444, issued to A. A. Munshi et al Nov. 1, 1988, discloses a method for allocating and optimizing register assignments during compiling of source into executable code in either a scalar or vector processor. The method uses a pebble game heuristic played on each basic block dependency graph for local optimization.
The aforementioned graph coloring methods utilize graphical analysis or an iterative analysis of a computer list representation of a directed graph which involve either heuristic determinations or a relatively complex computational analysis of a graphical representation to obtain local optimization. Direct global optimization, however, is not available. It is an object of the invention to provide an improved resource allocation arrangement resulting in an optimum assignment of resources in a process that uses global optimization in each allocation step.